Masala #0916

Metro $N$ ta bekatdan va $M$ ta bekatlarni o‘zaro bog‘lovchi yo‘llardan tashkil topgan. Agar $u$ va $v$ bekatlar orasida yo‘l mavjud bo‘lsa, unda $u$ dan $v$ ga yoki $v$ dan $u$ ga 1 daqiqada yetib borsa bo‘ladi.

Toshkent shahriga ko’chib kelgan Davlatbek metrodan ko‘p foydalana boshladi. Xususan bugun, Davlatbek $Q$ marta metrodan foydalanmoqchi. $i$-foydalanishida $a_i$ bekatdan $b_i$ bekatga borishi haqida aniq reja qildi. Agar metroni kutish va metro almashtirish vaqti inobatga olinmasa, Davlatbek har bir metrodan foydalanishida minimal necha daqiqa vaqtini metroda o‘tkazadi? Agar $i$-foydalanishi imkonsiz bo‘lsa −1 chiqaring.

Birinchi qatorda ikkita butun son - $N$ va $M$ $(2≤N≤300,1≤M≤ \dfrac{N(N−1)}{2})$ bekatlar soni va bekatlar orasidagi yo‘llari soni kiritiladi.

Keyingi $M$ ta qatorda ikkitadan butun son - $u_i$ va $v_i(1 ≤ v_i, u_i ≤ N )$ kiritiladi. Bu $u_i$ va $v_i$ bekatlar orasida yo‘l mavjud ekanligini anglatadi.

So‘ng yangi qatorda yagona butun son - $Q(1 ≤ Q ≤ 300)$ Davlatbekning bugun metrodan foydalanishlari soni kiritiladi.

Keyingi $Q$ ta qatorda ikkitadan butun son - $a_i$ va $b_i(1 ≤ a_i, b_i ≤ N )$, $i$-foydalanishdagi kirish va chiqish bekatlari kiritiladi.

$i$-foydalanish uchun $i$-qatorda $a_i$ bekatdan $b_i$ bekatga yetib borish uchun ketadigan minimal vaqtni chiqaring. Buning imkoni bo‘lmasa $−1$ chiqaring.